package recursion

type UpStairs struct {
	val map[int]int
}

// 上楼梯问题
/*
假设每次上楼梯可以跨1步，或2步
请求上n阶台阶一共有多少种走法
*/

func NewUpStairs() *UpStairs {
	return &UpStairs{
		map[int]int{},
	}
}

func (u *UpStairs) Up(n int) int {
	if u.val[n] != 0 {
		return u.val[n]
	}
	if n <= 1 {
		u.val[1] = 1
		return 1
	} else if n == 2 {
		u.val[2] = 2
		return 2
	} else {
		res := u.Up(n-1) + u.Up(n-2)
		u.val[n] = res
		return res
	}
}

func (u *UpStairs) Print(n int) int {
	return u.val[n]
}
